[BAEKJOON] 2831. 댄스 파티

Posted on August 19, 2021

문제 :

남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 사람과 춤을 출 수 있다.

모든 남자는 자신이 선호하는 여자와 춤을 추려고 한다. 각 남자가 선호하는 여자는 두 가지 유형이 있는데, 한 유형은 자신보다 키가 큰 여자이고, 다른 유형은 자신보다 키가 작은 유형이다. 여자도 남자와 마찬가지로 자신이 선호하는 남자와 춤을 추려고 한다. 각 여자가 선호하는 남자도 남자와 비슷하게 두 유형이 있다. (자신보다 키가 큰 남자, 작은 남자) 키가 같은 남자와 여자가 춤을 추는 일은 일어나지 않는다.

이때, 상근이는 각 사람의 키와 선호하는 이성 유형을 알고 있다. 이런 조건을 가지고 춤을 출 쌍을 만들어 주려고 한다. 상근이는 최대 몇 쌍을 만들 수 있을까?

입력 :

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 남자의 키가 밀리미터 단위로 주어진다. 키는 절댓값이 1500보다 크거나 같고, 2500보다 작거나 같은 정수이다. 사람의 키는 주어지는 값의 절댓값이다. 키가 양수인 경우에는 자신보다 키가 큰 여자와 춤을 추기를 원하는 남자이고, 음수인 경우에는 키가 작은 사람과 춤을 추기를 원하는 남자이다.

셋째 줄에는 여자의 키가 밀리미터 단위로 주어진다. 키의 범위나 의미 역시 남자와 동일하다.

출력 :

첫째 줄에 상근이가 만들어 줄 수 있는 쌍의 최댓값을 출력한다.

풀이 :

남성, 여성 파티원들의 키 선호를 따져 짝을 지어주는 문제이다.

우선 남자와 여자의 신장 정보를 활용하여 PersonInfo(신장, 키 선호, 매칭 여부 정보를 포함) 구조체를 만들어서 사용한다.

남성의 경우는 신장 오름차순 우선순위 큐를 만들어서 활용했으며, 여성의 경우는 신장 오름차순으로 정렬된 PersonInfo 구조체 배열을 활용한다.

매칭의 방법은 우선순위 큐와 소팅된 배열을 완성하게 되면 생각보다 간단하다.

우선순위 큐에서 신장이 작은 남성의 정보부터 차례로 꺼낸다.
남성이 작은 키를 선호할 경우에는 womanStartIdx 변수부터 차례로 여성 정보 배열을 훑어가며 매칭할 수 있는 정보를 찾는다 -> womanStartIdx는 여성 정보 배열의 가장 앞에서부터 설정되어 탐색한다.
남성이 큰 키를 선호할 경우에는 womanEndIdx 변수부터 차례로 여성 정보 배열을 훑어가면 매칭 정보를 찾는다 -> womanEndIdx 또한 여성 정보 배열 가장 앞에서부터 탐색한다.
신장 정보 순으로 소팅되어 있는 자료구조를 사용하기 때문에 탐색된 정보는 다시 탐색할 필요가 없다. 따라서 반복적인 탐색이 이루어지지 않아 시간복잡도를 효과적으로 줄일 수 있다.

코드 :

코드 보기/접기

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
struct PersonInfo {
    int height;
    bool likeGreater, isMatched;
};

struct compare {
    bool operator()(PersonInfo a, PersonInfo b) {
        return a.height > b.height;
    }
};

int n;

bool sorting(PersonInfo a, PersonInfo b) {
    return a.height < b.height;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int input, womanStartIdx = 0, womanEndIdx = 0, answer = 0;
    priority_queue<PersonInfo, vector<PersonInfo>, compare> pq;
    vector<PersonInfo> womanVec;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> input;
        if (input < 0) {
            pq.push(PersonInfo{input * -1, false, false});
        } else pq.push(PersonInfo{input, true, false});
    }

    for (int i = 0; i < n; i++) {
        cin >> input;
        if (input < 0) {
            womanVec.push_back(PersonInfo{input * -1, false, false});
        } else womanVec.push_back(PersonInfo{input, true, false});
    }
    sort(womanVec.begin(), womanVec.end(), sorting);

    while (!pq.empty()) {
        PersonInfo curPerson = pq.top();
        pq.pop();

        if (curPerson.likeGreater) {
            while (true) {
                if (womanEndIdx >= n) break;
                else if (womanVec[womanEndIdx].height > curPerson.height && !womanVec[womanEndIdx].likeGreater &&
                         !womanVec[womanEndIdx].isMatched) {
                    womanVec[womanEndIdx].isMatched = true;
                    womanEndIdx++;
                    answer++;
                    break;
                }
                womanEndIdx++;
            }
        } else {
            while (true) {
                if (womanVec[womanStartIdx].height < curPerson.height && womanVec[womanStartIdx].likeGreater &&
                    !womanVec[womanStartIdx].isMatched) {
                    womanVec[womanStartIdx].isMatched = true;
                    womanStartIdx++;
                    answer++;
                    break;
                } else if (womanVec[womanStartIdx].height >= curPerson.height) break;
                womanStartIdx++;
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++